public class test2 {
    //归并排序
    //这里定义为静态数组能避免重复开创数组
    int[] temp;

    public int[] sortArray(int[] nums) {
        temp = new int[nums.length];
        mergrSort(nums,0,nums.length-1);
        return nums;
    }

    public void mergrSort(int[] nums ,int left,int right){
        //递归出口
        if(left>=right){
            return;
        }
        //先排序两边
        int mid = (right+left)/2;
        mergrSort(nums,left,mid);
        mergrSort(nums,mid+1,right);
        //再合并两个有序数组
        int cur1 = left,cur2 = mid+1,i=0;
        while (cur1<=mid && cur2<=right){
            if(nums[cur1]<nums[cur2]){
                temp[i++] = nums[cur1++];
            }else{
                temp[i++] = nums[cur2++];

            }
        }
        //处理剩余未合并的数组
        while (cur1<=mid){
            temp[i++] = nums[cur1++];
        }
        while (cur2<=right){
            temp[i++] = nums[cur2++];
        }
        //重新赋予值给nums数组
        for(int j = left;j<=right;j++){
            nums[j] = temp[j-left];
        }
    }
}
